package com.demo.java.OD401_450.OD432;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【跳马问题(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146321302
 */
public class OdMain {
    static class Pair {
        int first;
        int second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    static final int[][] DIRECTIONS = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};  // 马的8个可能移动方向

    // BFS算法，计算一个马从某位置出发，能到达的最小步数
    static int[][] bfs4SingleHorse(int i, int j, int m, int n, int step) {
        int[][] mat = new int[m][n];
        for (int[] row : mat) {
            Arrays.fill(row, -1);  // -1表示不可达
        }

        mat[i][j] = 0;  // 起始位置的步数为0
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(i, j));
        int level = 0;

        while (!q.isEmpty()) {
            level++;
            if (level > step) {
                break;  // 达到最大步数，停止搜索
            }
            int qSize = q.size();
            for (int k = 0; k < qSize; k++) {
                Pair cur = q.poll();
                for (int[] dir : DIRECTIONS) {
                    int ni = cur.first + dir[0];  // 新位置的行坐标
                    int nj = cur.second + dir[1];  // 新位置的列坐标
                    if (0 <= ni && ni < m && 0 <= nj && nj < n && mat[ni][nj] == -1) {
                        mat[ni][nj] = level;  // 记录到达该位置的步数
                        q.add(new Pair(ni, nj));
                    }
                }
            }
        }
        return mat;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();  // 读取行数
        int n = scanner.nextInt();  // 读取列数

        scanner.nextLine(); // 消耗换行符

        String[][] grid = new String[m][n];
        for (int i = 0; i < m; i++) {
            String line = scanner.nextLine();
            String[] tokens = line.split(" ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = tokens[j];
            }
        }

        int[][] ansMat = new int[m][n];  // 初始化结果矩阵
        for (int[] row : ansMat) {
            Arrays.fill(row, 0);  // 将每个位置初始化为0
        }

        // 对每个马进行BFS计算
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!grid[i][j].equals(".")) {  // 如果该位置有马
                    int[][] mat = bfs4SingleHorse(i, j, m, n, Integer.parseInt(grid[i][j]));  // 计算该马的可达范围
                    for (int x = 0; x < m; x++) {
                        for (int y = 0; y < n; y++) {
                            if (mat[x][y] == -1 || ansMat[x][y] == -1) {
                                ansMat[x][y] = -1;  // 如果有任何马不能到达该位置，标记为不可达
                            } else {
                                ansMat[x][y] += mat[x][y];  // 否则累加步数
                            }
                        }
                    }
                }
            }
        }

        int ans = Integer.MAX_VALUE;  // 最小步数初始化为最大值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (ansMat[i][j] != -1 && ans > ansMat[i][j]) {
                    ans = ansMat[i][j];  // 查找最小的步数
                }
            }
        }

        System.out.println((ans == Integer.MAX_VALUE) ? 0 : ans);  // 如果最小步数没有更新，则返回0
    }
}
